package com.lg.partition11;

import java.io.*;
import java.util.HashMap;
import java.util.Map;

/**
 * @author `RKC`
 * @date 2022/5/10 8:14
 */
public class P1064NOIP2006提高组_金明的预算方案 {

    private static final int N = 65, M = 32010;
    private static Map<Integer, NodeMain> map = new HashMap<>(M);
    private static int[] f = new int[M];
    private static int n, m;

    private static StreamTokenizer tokenizer = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    private static PrintWriter writer = new PrintWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        m = nextInt(); n = nextInt();
        for (int i = 1; i <= n; i++) {
            int v = nextInt(), w = nextInt(), id = nextInt();
            if (id == 0) map.put(i, new NodeMain(v, w));
            else map.get(id).add(new Node(v, w));
        }
        writer.println(resolve());
        writer.flush();
    }

    private static int resolve() {
        for (NodeMain mm : map.values()) {
            for (int j = m; j >= 0; j -= 10) {
                for (int s = 0; s < 1 << mm.size; s++) {
                    int v = mm.v, w = mm.w * v;
                    for (int i = 0; i < mm.size; i++) {
                        if ((s >> i & 1) == 1) {
                            v += mm.ns[i].v;
                            w += mm.ns[i].v * mm.ns[i].w;
                        }
                    }
                    if (j >= v) f[j] = Math.max(f[j], f[j - v] + w);
                }
            }
        }
        return f[m];
    }

    private static class NodeMain {
        private int v, w;
        private Node[] ns = new Node[10];
        private int size;

        public NodeMain(int v, int w) {
            this.v = v;
            this.w = w;
        }

        public void add(Node n) {
            ns[size++] = n;
        }
    }

    private static class Node {
        private int v, w;

        public Node(int v, int w) {
            this.v = v;
            this.w = w;
        }
    }

    private static int nextInt() throws IOException {
        tokenizer.nextToken();
        return (int) tokenizer.nval;
    }
}
